package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/4/26 17:21
 */
public class C22 {


    public static List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (n == 0) return ans;
        process("", n, n, ans);
        return ans;
    }

    private static void process(String str, int restL, int restR, List<String> ans) {
        if (restL == 0 && restR == 0) {
            ans.add(str);
            return;
        }
        if (restL >= restR) {    // 如果剩余的左括号 >= 右括号. 只能使用左括号
            process(str + "(", restL - 1, restR, ans);
        } else {     // 剩余左括号 < 剩余右括号. 可先选左也可先选右
            if (restL > 0) {
                process(str + "(", restL - 1, restR, ans);
            }
            process(str + ")", restL, restR - 1, ans);
        }
    }


    public static void main(String[] args) {
        int n = 3;
        System.out.println(generateParenthesis(n));
    }

}
